#include <gtest/gtest.h>

using namespace ::std;

class Solution {
public:
    string addBinary(string a, string b);
};

// 超麻烦版本，有很多可以优化的空间
// 反转一下会方便很多，不如就反转一下吧。reverse(a.begin(), a.end());
string Solution::addBinary(string a, string b) {
	int sizeA = a.size(), sizeB = b.size();
	string biggerString, smallerString;
	int biggerSize, smallerSize;
	if(sizeA >= sizeB) {
		biggerString = a;
		smallerString = b;
		biggerSize = sizeA;
		smallerSize = sizeB;
	} else {
		biggerString = b;
		smallerString = a;
		biggerSize = sizeB;
		smallerSize = sizeA;
	}

	for(int i = 1; i <= smallerSize; ++i) {
		int biggerIndex = biggerSize - i, smallerIndex = smallerSize - i;
		int carry; // 进位
		char m = biggerString[biggerIndex], n = smallerString[smallerIndex];
		if(m == '1' && n == '1') {
			carry = 1;
			biggerString[biggerIndex] = '0';
		} else if(m == '1' || n == '1') {
			carry = 0;
			biggerString[biggerIndex] = '1';
		} else {
			carry = 0;
		}
		if(1 == carry) {
			int index = biggerIndex - 1;
			for(; index >= 0 && carry > 0; index--) {
				if(biggerString[index] == '0') {
					biggerString[index] = '1';
					carry = 0;
					break;
				} else if(biggerString[index] == '1') {
					biggerString[index] = '0';
					carry = 1;
				}
			}
			if(index < 0 && 1 == carry) {
				biggerString = "1" + biggerString;
				biggerSize++;
			}
			cout << biggerString << endl;
		}
	}
	cout << biggerString << endl;
	return biggerString;
}

class AddBinaryCheck : public ::testing::Test {
public:
	class Solution solution;
};

TEST_F(AddBinaryCheck, testAddBinary_1) {
	string a = "11", b = "1";
	EXPECT_TRUE("100" == solution.addBinary(a, b));
}

TEST_F(AddBinaryCheck, testAddBinary_2) {
	string a = "1010", b = "1011";
	EXPECT_TRUE("10101" == solution.addBinary(a, b));
}

TEST_F(AddBinaryCheck, testAddBinary_3) {
	string a = "1111", b = "1111";
	EXPECT_TRUE("11110" == solution.addBinary(a, b));
}

int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}
